package com.wq.struct;

import java.util.Stack;

/**
 * @Author: wangqiang20995
 * @Date:2019/2/27
 * @Description:
 * @Resource:
 */
public class BinaryTreeStruct extends Struct {

    private Node root;

    private int search = 0;//0,1,2 分别代表先序，中序，后序遍历

    public void addNode(int number) {
        if (root == null) {
            root = new Node(number);
        } else {
            //查找一个不存在的节点，然后插入
            Node temp = root;
            while (true) {
                if (number < temp.number) {
                    if (temp.left == null) {
                        temp.left = new Node(number);
                        return;
                    } else {
                        temp = temp.left;
                    }
                } else {
                    if (temp.right == null) {
                        temp.right = new Node(number);
                        return;
                    } else {
                        temp = temp.right;
                    }
                }
            }
        }
    }


    public Node findNode(int value) {
        if (empty()) {
            throw new IllegalStateException("二叉树为空");
        }

        Node trail = root;
        while (true) {
            if (value < trail.number) {
                if (trail.left == null) {
                    System.out.println("二叉树中找不到-->" + value);
                    return null;
                }
                trail = trail.left;
            } else if (value > trail.number) {
                if (trail.right == null) {
                    System.out.println("二叉树中找不到-->" + value);
                    return null;
                }
                trail = trail.right;
            } else {
                System.out.println("找到节点-->" + trail);
                return trail;
            }
        }
    }

    public void deleteFromTree(int value) {
        if (empty()) {
            throw new IllegalStateException("二叉树为空");
        }

        Node node = findNode(value);

        Node nodeParent = findParent(node);

        boolean isLeft = nodeParent.left == node;

        if (node == null) {
            throw new IllegalArgumentException("二叉树中找不到对应元素，无法删除");
        }

        if (node.left == null && node.right == null) {//要删除的节点没有子节点
            Node parent = findParent(node);

            if (node.number < parent.number) {
                parent.left = null;
            } else {
                parent.right = null;
            }

            return;
        }

        if (node.left == null || node.right == null) {//要删除的节点只有一个子节点
            Node parent = findParent(node);
            if (node.number < parent.number) {//当前node属于parent的左节点
                if (node.left != null) {
                    parent.left = node.left;
                    node.left = null;
                } else {
                    parent.left = node.right;
                    node.right = null;
                }
            } else {//node属于parent的右节点
                if (node.left != null) {
                    parent.right = node.left;
                } else {
                    parent.right = node.right;
                }
            }

            return;
        }

        if (node.left != null && node.right != null) {
            //首先找到当前节点的后继节点
            Node successor = node.right;
            while (successor.left != null) {
                successor = successor.left;
            }

            Node parent = findParent(successor);

            if (node.right.left == null) {//右子节点没有左子节点，那么这个节点就是后继节点
                if (node == root) {
                    successor.left = node.left;
                    root = successor;
                } else if (!isLeft) {//要删除的节点是parent的右节点
                    parent.right = successor;
                    successor.left = node.left;
                } else {//要删除的节点是父节点的左节点
                    parent.left = successor;
                    successor.left = node.left;
                }
            } else {//右子节点含有左子节点
                parent.left = successor.right;
                successor.right = node.right;
                if (node == root) {
                    root = successor;
                    root.left = node.left;
                } else if (isLeft) {
                    nodeParent.left = successor;
                    successor.left = node.left;
                } else {
                    nodeParent.right = successor;
                    successor.left = node.left;
                }

            }
        }
    }

    public Node findParent(Node child) {
        Node trailNode = root;

        if (child == trailNode) {
            throw new IllegalArgumentException("root节点没有parent");
        }

        while (true) {
            if (child.number < trailNode.number) {
                if (trailNode.left == null) {
                    throw new IllegalArgumentException("node[" + child + "]不存在");
                }

                if (trailNode.left == child) {
                    return trailNode;
                } else {
                    trailNode = trailNode.left;
                }
            } else if (child.number > trailNode.number) {
                if (trailNode.right == null) {
                    throw new IllegalArgumentException("node[" + child + "]不存在");
                }

                if (trailNode.right == child) {
                    return trailNode;
                } else {
                    trailNode = trailNode.right;
                }
            } else {
                return trailNode;
            }
        }
    }

    public boolean empty() {
        return root == null;
    }

    public void setSearch(int search) {
        this.search = search;
    }

    public static void main(String args[]) {
        BinaryTreeStruct binaryTreeStruct = new BinaryTreeStruct();
        binaryTreeStruct.setSearch(2);

        binaryTreeStruct.addNode(50);
        binaryTreeStruct.addNode(45);
        binaryTreeStruct.addNode(75);
        binaryTreeStruct.addNode(62);
        binaryTreeStruct.addNode(84);
        binaryTreeStruct.addNode(81);
        binaryTreeStruct.addNode(87);
        binaryTreeStruct.addNode(80);
        binaryTreeStruct.addNode(82);
        binaryTreeStruct.addNode(76);
        binaryTreeStruct.addNode(79);

        binaryTreeStruct.printStruct();

        Node find = binaryTreeStruct.findNode(80);

        Node parent = binaryTreeStruct.findParent(find);

        binaryTreeStruct.describeNode(parent);

//        System.out.println("删除没有子节点的叶子节点");
//        binaryTreeStruct.deleteFromTree(82);
//        binaryTreeStruct.printStruct();

//        System.out.println("删除有一个子节点的节点");
//        binaryTreeStruct.deleteFromTree(80);
//        binaryTreeStruct.printStruct();

        System.out.println("删除有两个子节点的节点");
        binaryTreeStruct.deleteFromTree(75);
        binaryTreeStruct.printStruct();
    }

    private void describeNode(Node node) {
        System.out.println("Node{number:" + node + ",left:" + node.left + ",right:" + node.right + "}");
    }

    @Override
    protected void printStruct() {
        switch (search) {
            case 0:
                System.out.println("先序遍历");
                beforeSearch(root);
                break;

            case 1:
                System.out.println("中序遍历");
//                middleSearch(root);
                middleInRecursion(root);
                break;

            case 2:
                System.out.println("后序遍历");
//                afterSearch(root);
                afterInRecursion(root);
                break;
        }
        System.out.println();
    }

    private void afterSearch(Node root) {
        if (root != null) {
            afterSearch(root.left);
            afterSearch(root.right);
            System.out.printf("%d\t", root.number);
        }
    }

    private void afterInRecursion(Node root){
        Stack<Node> stack = new Stack<>();

        Node node = root;
        while (true){
            if(node != null){
                stack.push(node);
                node = node.left;
            }else {
                if(stack.isEmpty()){
                    return;
                }

                if(stack.peek().right == null){
                    node = stack.pop();
                    System.out.printf("%d\t",node.number);
                    //判断leaf节点的父节点的右子节点，是否是这个leaf节点

                    while (stack.peek().right == node){
                        node = stack.pop();
                        System.out.printf("%d\t",node.number);

                        if(stack.isEmpty()){
                            break;
                        }
                    }
                }

                if(!stack.isEmpty()){//执行到这里，说明某个节点的左子树已经遍历完了，此时需要遍历右子树
                    node = stack.peek().right;
                }else {
                    node = null;
                }
            }
        }
    }

    private void beforeSearch(Node root) {
        if (root != null) {
            System.out.printf("%d\t", root.number);
            beforeSearch(root.left);
            beforeSearch(root.right);
        }
    }

    private void beforeInRecursion(Node root) {
        Stack<Node> stack = new Stack<>();
        Node node = root;
        while (true) {
            while (node != null) {
                System.out.printf("%d\t", node.number);
                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            node = stack.pop();
            node = node.right;
        }
    }


    /**
     * @Author:wangqiang20995
     * @Datetime:2019/2/28 10:00
     * @param: [node]
     * @Description:中序遍历-递归
     **/
    private void middleSearch(Node node) {
        if (node != null) {
            middleSearch(node.left);
            System.out.printf("%d\t", node.number);
            middleSearch(node.right);
        }
    }


    /**
     * @Author:wangqiang20995
     * @Datetime:2019/2/28 10:01
     * @param: []
     * @Description:中序遍历，非递归
     **/
    private void middleInRecursion(Node root) {
        Stack<Node> stack = new Stack<>();

        Node rootNode = root;
        while (true) {

            while (rootNode != null) {
                stack.push(rootNode);
                rootNode = rootNode.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            Node node = stack.pop();
            describeNode(node);
            rootNode = node.right;
        }
    }

    private class Node {
        private int number;
        private Node left;
        private Node right;

        public Node(int number) {
            this.number = number;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "number=" + number +
                    '}';
        }
    }
}
